package h0808;
import java.util.*;
/**
  * @description 叠积木
  * @author 不知名帅哥
  * @date 2024/8/8 10:33
  * @version 1.0
*/
public class StackingBlocks {
    /**
     * 叠积木
     * TODO 这道题目类似于 leetcode 698. 划分为k个相等的子集
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Integer[] nums = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        System.out.println(getResult(nums));
    }

    private static int getResult(Integer[] nums) {
        int n= nums.length;
        //如果只有一个积木,那么只能是一层高度
        if (n==1){
            return 1;
        }
        //如果有两个积木
        if (n==2){
            //如果两个积木长度相同,则最大高度是2
            //如果两个积木长度不同,则最大高度为1
            return nums[0]-nums[1]!=0?1:2;
        }
        //积木按照长度降序
        Arrays.sort(nums, (a, b) -> b-a);

        //TODO 一层的最小长度,即最长的积木长度
        int minLen=nums[0];
        //TODO 一层的最大长度
        int maxLen=nums[0]+nums[nums.length-1];

        //尝试minLen和maxLen中每一个值作为一层长度
        for (int len = minLen; len < maxLen; len++) {
            //对应一层长度限制下的最大高度
            int height=0;

            //通过l,r指针去选择组成一层的一个或两个积木
            //l指针指向最大长度的积木
            int l=0;
            //r指针指向最小长度的积木
            int r=n-1;

            //如果最大长度的积木,可以独立一层,则l++,height++
            //TODO 能独立成组的,必是长度最大的.如果还有别的积木组合和大于此即积木,就不符合题意.
            while (l<n&&nums[l]==len){
                l++;
                height++;
            }

            //TODO 注重理解
            //如果l,r积木无法组成一层
            //假设nums[l]+nums[r]>length,则必然nums[l]+nums[r-1]>length
            //因为nums已经降序,nums[r-1]>=nums[r],即必然l积木无法和其他积木组成一层
            //假设nums[l]+nums[r]<length,则必然nums[l+1]+nums[r]<length,
            //因为nums已经降序,nums[l+1]<=nums[l],即比如你r积木无法和其他积木组成一层
            while (l<r){
                if (nums[l]+nums[r]!=len) break;
                l++;
                r--;
                height++;
            }
            //如果正常结束,则必然l>r,否则就是异常结束
            if (l<=r) continue;
            return height;
        }
        return -1;
    }

}
